package sort;

import java.util.Arrays;
import java.util.Scanner;
/**
 * @ClassName: heap
 * @Auther: Drawin
 * @Date: 2021/9/20 22:45
 * @Description:
 */

public class heap {
/**
 * 构建大顶堆
 */
public static void adjustHeap(int[]a,int i,int len){
    int temp,j;
    temp=a[i];
    for(j=2*i;j<len;j*=2){//沿大节点向下筛选
        if(j<len&&a[j]<a[j+1])
            ++j;//j 为关键字中较大记录的下标
        if(temp>=a[j])
            break;
        a[i]=a[j];
        i=j;
    }
    a[i]=temp;
}
public static void heapSort(int[] a){
    int i;
    for(i=a.length/2-1;i>=0;i--){//构建一个大顶堆
        adjustHeap(a,i,a.length-1);
    }
    for(i=a.length-1;i>=0;i--){//将堆顶记录和当前未经排序的子序列的最后一个记录交换
        int temp=a[0];
        a[0]=a[i];
        a[i]=temp;
        adjustHeap(a,0,i-1);//将a中前i-1个记录重新调整为大顶堆
    }
}

    public static void main(String[] args) {
        System.out.println("请输入数组个数：");
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        int[]a=new int [n];
        for(int i=0;i<a.length;i++){
            a[i]=s.nextInt();
        }
        heapSort(a);
        System.out.println(Arrays.toString(a));
    }
}
